Sự đàn áp tàn bạo của các đội lính tử thần của nhà độc tài Fulgencio Batista ở Yara đã thúc đẩy Puebla hỗ trợ các nhà bất đồng chính kiến chống chính phủ từ khi còn nhỏ.[4] Năm 1956, cô bỏ học trường ở Manzanillo để tham gia Phong trào 26 tháng 7 (M-26-7) của quân nổi dậy cộng sản chiến đấu nhằm lật đổ chế độ của Batista. Sự hỗ trợ bí mật của cô cho phong trào bao gồm buôn lậu vũ khí, thuốc men và tiền cho phiến quân. Puebla cũng tham gia phá hoại ở mức thấp chống lại chính phủ, như cắt đường dây điện và đâm lốp xe cảnh sát.[5] Năm 1957, cô đã đi vào vùng núi Sierra Maestra để gia nhập quân đội phiến quân sau khi sự hợp tác của cô với phiến quân đã bị bại lộ cho chính phủ bởi lời khai từ một thành viên M-26-7 bị bắt.[2][6] Trong Sierras, cô đã gặp và làm việc với nhà tổ chức nổi dậy Celia Sánchez, "mẹ" của lực lượng phiến quân.[7]

Thủ lĩnh phiến quân Fidel Castro đã thành lập Trung đội nữ Mariana Grajales vào tháng 9 năm 1958, một nhóm gồm mười ba phụ nữ mà ông ta đích thân dạy bắn. Fidelidel tuyên bố trung đội sẽ là đơn vị vệ sĩ cá nhân của ông. Puebla nắm vai trò chỉ huy thứ hai.[3][8] Trung đội đã tham gia chiến đấu nhiều trận và đóng vai trò là tình báo cho quân đội. Họ đã chế ra súng M1 Carbine, có trọng lượng nhẹ hơn và dễ mang theo hơn so với vũ khí thường được phát cho phiến quân chiến binh du kích.[9]